\section{聚类算法}
通过模糊粗糙集, 我了解到了一些聚类算法, 知道了软聚类的存在(之前的思维里面一直只有硬聚类的想法, 从来不知道软聚类的存在, 可以感叹一下模糊数学的应用太广泛了!), 接下来介绍一下硬聚类和软聚类的定义.
\begin{defn}[硬聚类]
    将论域 $U$ 分为 $k$ 类, $\left\{ D_1,D_2,\cdots,D_k \right\}$ .且有 
    $$ \begin{aligned}
        \bigcup_{i=1}^k D_i &= U\\ 
        D_i\bigcap D_j &= \varnothing, i\ne j
    \end{aligned} $$
    则叫做硬聚类.
\end{defn}

\begin{defn}[软聚类]
    将论域 $U$ 分为 $k$ 类, $\left\{ D_1,D_2,\cdots,D_k \right\}$. 且每一类都是 $U$  的一个模糊集合:
    $$ D_i:U\to [0,1] $$
    $D_i(x)$ 代表 $x$ 属于 $D_i$ 的程度.这样的聚类叫做软聚类.
\end{defn}


在假期的时候看到了用 c-means\cite{bezdek_fcm_1984}、c-means++\cite{stetco_fuzzy_2015}、 fuzzy rough c-means(frcm)\cite{yu_frcm_2024}和谱聚类\cite{2004A}.

下面简单介绍一下 c-means 和 frcm

\subsection{Fuzzy C-Means 算法}
设论域为 $U$ , 指定的类别数为 $k$ , 即有 $k$ 个类别 $\left\{ D_1,D_2,\cdots,D_k \right\}$ .
每个类别都是一个模糊集 
$$ D_i:U\to [0,1], i=1,2,\cdots,k $$
指的是 $U$ 中的元素属于这个类别的程度. 令 $\mu_{ij}=D_j(x_i)$ ,所以 $A = (\mu_{ij})_{|U|\times k}$ 就是一个矩阵.
然后每个类别应该会有个中心, 我们记作 $c_j$ , 代表第 $j$ 列的中心.

我们的目的是优化目标函数 
$$ \begin{aligned}
    J_{FCM} = \sum_{i=1}^{|U|}\sum_{j=1}^{k} \mu_{ij}^m \fan{x_i-c_i}^2 \\ 
    \mathrm{s.t.} 0\le \mu_{ij}\le 1,\sum_{j=1}^k \mu{ij} = 1.
\end{aligned} $$
使用 Lagrange 乘数法得到 
$$ 
\begin{aligned}
    \mu_{ij} &= \left( \sum_{g=1}^{k}\left( \frac{\fan{x_i-c_j}^2}{\fan{x_i-c_g}^2} \right)^{(\frac{1}{m-1})} \right)^{-1}\\ 
    c_j &= \frac{\sum_{i=1}^{|U|}\mu_{ij}^mx_i}{\sum_{i=1}^{|U|}\mu_{ij}^m}.
\end{aligned}
$$

只需要迭代到矩阵 $A$ 或者每个中心变化的量小于一个定值即可. 算法流程如下
\input{algorithm/cmeans.tex}


\subsection{Fuzzy Rough C-Means(RFCM) 算法}
在改造C-Means 算法的时候, 人们就喜欢从两个方面下手, 第一个是矩阵 $A$, 即 $x$ 对每个类的隶属度, 另一方面是计算中心的方法, 在FCM中使用的是 Lagrange 乘数法去计算中心, 接下来介绍的是另一种计算中心的算法.   
这个算法利用了模糊粗糙集，他的模糊关系为模糊相似关系，使用了高斯核函数.
\begin{defn}
    Let $S=\left\{ U,A,V,F \right\}$ be an IS and $x, y\in U$ . The fuzzy similarity relationship $(R_{kernel})$ between $x$ and $y$ is defined as follows:
    \begin{equation}
        R_{kernel}(x,y)=\exp{\left( -\frac{\fan{x-y}^2}{2\sigma^2} \right)}
    \end{equation}
\end{defn}

接下来，要指定有 $k$ 个分类, 就有 $C_1,C_2,\cdots,C_k$ , 接下来我们求 $x\in C_i$ 的上下近似(在我看来是似然测度和信任测度)
\begin{defn}
    Let $S=\left\{ U,A,V,F \right\}$ be an IS, $\mu_{C_i}(y)$ be the membership degree of $y$ to cluster $C_i$ and $x\in U$ . The definition of fuzzy 
    rough operators based on kernel similarity is defined as follows:
    $$ \begin{aligned}
        \overline{R_{kernel}}(\mu_{C_i})(x) &= \bigvee_{y\in U}\left( R_{kernel}(x,y)\bigwedge \mu_{C_i}(y) \right); \\ 
        \underline{R_{kernel}}(\mu_{C_i})(x) &= \bigwedge_{y\in U}\left( \left( 1-R_{kernel}(x,y) \right)\bigvee \mu_{C_i}(y) \right).
    \end{aligned} $$    
\end{defn}
在原文中是这样写的 
\begin{framed}
    In the definition provided, we extend the classical fuzzy rough set’s upper and lower approximation operators by incorporating kernel similarity between objects and the membership degree of objects to the target cluster. In the expression $\overline{R_{kernel}}(\mu_{C_i})(x)$, the $\bigwedge$ operator plays a crucial role in assessing the current membership degree. It comprehensively evaluates the membership degree of sample $x$ to cluster $C_i$. The $\bigvee$ operator, on the other hand, controls the final value by considering the maximum membership degree obtained from the kernel similarity between the sample $x$ and the target cluster. Consequently, the membership degree of $x$ to the approximate set on $\mu_{Ci}$ depends on the maximum value derived from the kernel similarity calculation in the universe and the target cluster. In $\underline{R_{kernel}}(\mu_{C_i})(x)$, the expression $1 − {R_{kernel}}(x,y)$ represents the inverse of the kernel similarity between the sample $x$ and the domain object $y$. It captures the dissimilarity between the target object $x$ and object $y$ from the domain $U$ , considering both the dissimilarity and the membership of $y$ with respect to cluster $C_ii$. The $\bigwedge$ operator again controls the final value, cleverly addressing the situation where the kernel similarity is equal to $1$. By incorporating these definitions of the upper and lower approximation operators, we can effectively capture the fuzzy boundaries and dissimilarities between objects and clusters. This approach allows for a more comprehensive and accurate representation of the membership degrees in fuzzy rough sets, enabling better handling of uncertain and fuzzy data.

    我的大概翻译:是在所提供的定义中，我们通过结合对象之间的核相似性和对象对目标聚类的隶属度，扩展了经典模糊粗糙集的上下近似算子。在表达式$\overline{R_{kernel}}(\mu_{C_i})(x)$中，算子在评估当前隶属度方面起着至关重要的作用。它综合评价样本$x$对聚类$C_i$的隶属度。另一方面，运算符通过考虑从样本$x$和目标聚类之间的核相似性获得的最大隶属度来控制最终值。因此，$x$对$\mu_{Ci}$上近似集的隶属度取决于从论域和目标簇中的核相似性计算导出的最大值。在$\underline{R_{kernel}}(\mu_{C_i})(x)$中，表达式$1 − {R_{kernel}}(x,y)$表示样本$x$和域对象$y$之间的核相似性的逆。它从论域 $U$ 捕获目标对象 $x$ 和对象 $y$ 之间的相异性，考虑相异性和$y$相对于聚类$C_i$的成员资格。合取运算控制最终值，巧妙地解决了核相似度等于1的情况。通过结合上下近似算子的这些定义，我们可以有效地捕捉对象和聚类之间的模糊边界和不相似性.这种方法允许更全面和准确地表示模糊粗糙集中的隶属度，能够更好地处理不确定和模糊数据.
\end{framed}
上近似我还是很理解, 离得越近且 $y\in C_i$ 的程度越大那上近似的值越高是肯定的. 但是下近似的话要求相似度和 $y\in C_i$ 的程度取大最后再取小很不理解. 另外一个不理解的点是, 这个上下近似是在说 $x\in C_i$ 的信任测度和似然测度吗? 我觉得是这样的情况. 

接下来他给了一个指标: 模糊粗糙度(Fuzzy Rough Degree,FRD), 应该是类比经典粗糙集的精确度和粗糙度构造的一个量. 
\begin{defn}
    Let $S=\left\{ U,A,V,F \right\}$ be an IS, $k$ be the number of clusters, $C_i$ be the i-th cluster and $x\in U$ . The fuzzy rough degree(FRD) is defined as follows:
    $$ FRD(x,C_i) = \frac{\overline{R_{kernel}}(\mu_{C_i})(x)}{\underline{R_{kernel}}(\mu_{C_i})(x)}. $$
\end{defn} 
上近似和下近似越接近1 应该越好, 因为此时模糊粗糙度越小, 那聚类的不确定性就越低. 所以 $x\in U$, 那 $x$ 应该属于什么类呢? 他就把所有 $FCR(x,C_i)$ 最小的那些 $C_i$ 找出来做成一个集合, 叫为 $\mathbb{C}_i$.  
\begin{defn}
    Let $S=\left\{ U,A,V,F \right\}$ be an IS, $\mathbb{C}(\mathbb{C}=\left\{ C_1,C_2,\cdots,C_k \right\})$ be the set of clusters and $x\in U$ . The set of cluster $\mathbb{C}_x$ to which $x$ belongs is defined as follows:
    $$ \mathbb{C}_x = \left\{ C_j\in \mathbb{C} \Big|FRD(x,C_j)=\min_{C_i\in \mathbb{C} }(FRD(x,C_i)) \right\} $$

\end{defn}
接下来从 $\mathbb{C}_x$ 中随机抽一个当成 $x$ 属于的类, 然后通过这个数据来更新中心点, 更新元素和类之间的隶属矩阵. 算法大致如(算法\ref{algo:FRCM}):
\input{algorithm/frcm.tex}
\input{sections/谱聚类教程.tex}
\subsection{实验}
\subsubsection{数据集和比较算法}

实验采用 UCI 中的数据集和人工数据集, 数据集的信息表如表 \ref{tab:t2}. 其中 UCI 数据用前三种聚类方法
, 人工数据采用 Kmeans, AffinityPropagation,MeanShift,SpectralClustering, ward, AgglomerativeClustering,DBSCAN,OPTICS,Birch,GaussianMixture 十种方法进行聚类.

\begin{table}[htbp]
    \centering
    \caption{数据集}
    \label{tab:t2}
    \setlength{\tabcolsep}{1cm}
    \begin{tabular}{cccc}
        \toprule
        DataSets & Size & Dimensions & Classes\\
        \midrule
        iris     & 150  & 4          & 3 \\ 
        seeds    & 199  & 7          & 3 \\
		\midrule
		circles  	 & 1500 & 2			 & 2  \\ 
		moons    	 & 1500 & 2		     & 2  \\ 
		varied   	 & 1500 & 2 		 & {} \\
		line 	 	 & 1500 & 2 		 & 3  \\ 
		blobs    	 & 1500 & 2			 & 3  \\ 
		no structure & 1500 & 2 		 & {} \\
        \bottomrule
    \end{tabular}
\end{table}
\subsubsection{四种算法的聚类结果}
我们用 C-Means, FRCM, K-Means, Spectral Clustering之间比较, 比较结果如下


\begin{figure}[H]
	\centering
	\begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/kmeans/kmeans1.png}
		\caption{K-Means in Iris}
		\label{fig:kmeans_iris}%文中引用该图片代号
	\end{minipage}
	\begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/cmeans/cmeans1.png}
		\caption{C-Means in Iris}
		\label{fig:cmeans1}%文中引用该图片代号
	\end{minipage}
	%\qquad
	%让图片换行，
\end{figure}
\begin{figure}[H]
	\begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/frcm/frcm1.png}
		\caption{Fuzzy Rough C-Means in Iris}
		\label{fig:frcm1}%文中引用该图片代号
	\end{minipage}
	\begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/original/original.png}
		\caption{Iris Original Data}
		\label{fig:original}%文中引用该图片代号
	\end{minipage}
\end{figure}
\begin{figure}[H]
	\begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/kmeans/seeds_kmeans.png}
		\caption{K-Means in Seeds}
		\label{fig:kmeanseed}%文中引用该图片代号
	\end{minipage}
    \begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/cmeans/seeds.png}
		\caption{C-Means in Seeds}
		\label{fig:cmeanseed}%文中引用该图片代号
	\end{minipage}
\end{figure}
\begin{figure}[H]
    \begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/frcm/frcm_seeds.png}
		\caption{Fuzzy Rough C-Means in Seeds}
		\label{fig:frcmseed}%文中引用该图片代号
	\end{minipage}
    \begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/original/seeds_original.png}
		\caption{Seeds Original Data}
		\label{fig:seedsori}%文中引用该图片代号
	\end{minipage}
\end{figure}
\begin{figure}[H]
    \begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/spectral/spectral_iris.png}
		\caption{Spectral Clustering in Iris}
		\label{fig:sciris}%文中引用该图片代号
	\end{minipage}
    \begin{minipage}{0.49\linewidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/spectral/spectral_seeds.png}
		\caption{Spectral Clustering in Seeds}
		\label{fig:scseeds}%文中引用该图片代号
	\end{minipage}
\end{figure}
可见效果还可以(具体的评价聚类的一些指标没有做, 只做了一些效果图).

\subsubsection{十种算法的聚类结果}
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{figures/Figure_2.png}
	\caption{Result of Ten Clustering Algorithm}
	\label{fig:ten_clustering}

\end{figure}